#include <cstdlib>
#include <iostream>
#include <vector>


using namespace std;
const int MAX=10000;

void composantes(int n, int m, int edge[][2], int comp[]);
void grapheRandom(int n, int m, int edge[][2]);
void affichage(int n, int m, int edge[][2],int comp[]);
void ecritureTaille(int n, int m, int comp[]);



int main(){ 

   int n;     // Nombre de sommets.	
    int m;     // Nombre d'aretes.	
    cout << "Entrer le nombre de sommets:";
    cin >> n;
    cout << "Entrer le nombre d'aretes:";
    cin >> m;

    int edge[MAX][2];    // Tableau des aretes.
    int comp[MAX];       // comp[i] est le numero de la composante contenant i.

	grapheRandom(n,m,edge);
	composantes(n,m,edge,comp);
	//affichage(n, m, edge, comp);

	ecritureTaille(n,m,comp);


    return 0;
}


 

void affichage(int n, int m, int edge[][2], int comp[MAX]){

	for(int i(0); i<m; i++){
	
		cout<<"("<<edge[i][0]<<","<<edge[i][1]<<")"<<endl;
	}

	for(int j(0); j<n; j++){

		cout<<"comp["<<j<<"]="<<comp[j]<<endl;
	}


}

void grapheRandom(int n, int m, int edge[][2]){

		srand(time(NULL));

		for(int i(0); i<m; i++){

				edge[i][0]=rand()%n;
			do{
				
				edge[i][1]=rand()%n;
		
			}while(edge[i][0]==edge[i][1]);
		}


}

void composantes(int n, int m, int edge[][2], int comp[]){
	int aux;

		for(int i(0); i<n;i++){
		
			comp[i]=i;
		}

		for(int j(0); j<m; j++){

			if(edge[j][0]!=edge[j][1])
				aux=edge[j][0];

		
			for(int k(0); k<n; k++){

				if(comp[k]==aux)
					comp[k]=comp[edge[j][1]];

			}	
	
	
		}





}


void ecritureTaille(int n, int m, int comp[]){
	
	int temp[MAX];
	int nbComp[MAX];
		
	
	for(int i(0); i<n; i++){
		
		temp[comp[i]]++;
		
	}
	
	for(int j(0); j<n; j++){
		
		if(temp[comp[j]]==1)
			nbComp[1]++;
		
		else if(temp[comp[j]]>1)
			nbComp[temp[j]]++;
	
	}
	
	
	cout<<"\nil y a "<<nbComp[1]<<" points isolés"<<endl;
	
	for(int k(2); k<n; k++){
		
		if(nbComp[k]>0)
			cout<<"il y a "<<nbComp[k]<<" composantes de taille "<<k<<endl;
	
	
	}
	
}

